0221. 最大正方形【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

---

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

---

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

2. 🎯 s.1 - 动态规划

c

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize, n = matrixColSize[0], maxSide = 0;
    int** dp = (int**)calloc(m + 1, sizeof(int*));
    for (int i = 0; i <= m; i++) dp[i] = (int*)calloc(n + 1, sizeof(int));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                int a = dp[i - 1][j], b = dp[i][j - 1], c = dp[i - 1][j - 1];
                int mn = a < b ? a : b;
                dp[i][j] = (mn < c ? mn : c) + 1;
                if (dp[i][j] > maxSide) maxSide = dp[i][j];
            }
        }
    }
    for (int i = 0; i <= m; i++) free(dp[i]);
    free(dp);
    return maxSide * maxSide;
}

js

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  const m = matrix.length,
    n = matrix[0].length
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  let maxSide = 0
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (matrix[i - 1][j - 1] === '1') {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        maxSide = Math.max(maxSide, dp[i][j])
      }
    }
  }
  return maxSide * maxSide
}

py

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_side = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == '1':
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    max_side = max(max_side, dp[i][j])
        return max_side * max_side

• 时间复杂度：$O(m\times n)$，其中 $m$ 和 $n$ 是矩阵的行数和列数
• 空间复杂度：$O(m\times n)$，dp 数组

算法思路：

• $dp[i][j]$ 表示以 $(i,j)$ 为右下角的最大正方形边长
• 转移方程：$dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1$
• 最终答案为最大边长的平方